package algorithmlearn.sort;

/*
二分查找  对 有重复 数据的有序的数据集合
几种变体
    1. 查找最后一个值等于给定值的元素
    2. 查找第一个大于等于给定值的元素
    3. 查找最后一个小于等于给定值的元素
 */
public class BinarySearch3 {
    public static void main(String[] args) {
        int[] array = {1, 2, 2, 4, 5, 6, 7, 7, 8, 8, 8, 9, 10, 16, 17, 17, 19, 20, 23};
        System.out.println(bsearch1(array, array.length,8));
        System.out.println(bsearch2(array, array.length,8));
        System.out.println(bsearch3(array, array.length,8));
    }

    //1.查找最后一个值等于给定值的元素
    public static int bsearch1(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid =  low + ((high - low) >> 1);
            if (a[mid] > value) {
                high = mid - 1;
            } else if (a[mid] < value) {
                low = mid + 1;
            } else {
                if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
                else low = mid + 1;
            }
        }
        return -1;
    }

    //2. 查找第一个大于等于给定值的元素
    public static int bsearch2(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid =  low + ((high - low) >> 1);
            if (a[mid] >= value) {
                if ((mid == 0) || (a[mid - 1] < value)) return mid;
                else high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    //3. 查找最后一个小于等于给定值的元素
    public static int bsearch3(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid =  low + ((high - low) >> 1);
            if (a[mid] >= value) {
                if ((mid == 0) || (a[mid - 1] < value)) return mid;
                else high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
}
